//
//  HD_LD_ClusterQuadtree.m
//  HDWuDaDaoServiceCenter
//
//  Created by mac on 2017/7/12.
//  Copyright © 2017年 HDNiuKuiming. All rights reserved.
//

#import "HD_LD_ClusterQuadtree.h"

#define MAX_POINTS_PER_NODE 40

#define PointParameter 8.0

@implementation HD_LD_ClusterQuadtree

- (id)initWithRect:(CGRect) rect
{
    self = [super init];
    if (self) {
        _quadItems = [[NSMutableArray alloc] initWithCapacity:MAX_POINTS_PER_NODE];
        _rect = rect;
    }
    return self;
}

- (void)addItem:(HDAnnotation *)quadItem{
    if (quadItem == nil) {
        return ;
    }
    if ([self rect:_rect containsPt:quadItem.point] == NO) {
        return;
    }
    
    if(_quadItems.count < MAX_POINTS_PER_NODE) {
        [_quadItems addObject:quadItem];
        return ;
    }
    
    if(_childrens == nil || _childrens.count == 0) {
        [self subdivide];
    }
    for (HD_LD_ClusterQuadtree *children in _childrens) {
        [children addItem:quadItem];
    }

}

//rect是否包含pt
- (BOOL)rect:(CGRect) rect  containsPt:(CGPoint) pt {
    return rect.origin.x <= pt.x && pt.x <= (rect.size.width + rect.origin.x) && rect.origin.y <= pt.y && pt.y <= (rect.size.height + rect.origin.y);
}
//四叉树拆分
- (void)subdivide {
    _childrens = [[NSMutableArray alloc] initWithCapacity:4];
    CGFloat x = _rect.origin.x;
    CGFloat y = _rect.origin.y;
    CGFloat w = _rect.size.width / 2.f;
    CGFloat h = _rect.size.height / 2.f;
    [_childrens addObject:[[HD_LD_ClusterQuadtree alloc] initWithRect:CGRectMake(x, y, w, h)]];
    [_childrens addObject:[[HD_LD_ClusterQuadtree alloc] initWithRect:CGRectMake(x + w, y, w, h)]];
    [_childrens addObject:[[HD_LD_ClusterQuadtree alloc] initWithRect:CGRectMake(x, y + h, w, h)]];
    [_childrens addObject:[[HD_LD_ClusterQuadtree alloc] initWithRect:CGRectMake(x + w, y + h, w, h)]];
}

///获取rect范围内的BMKQuadItem
- (NSArray*)searchInRect:(CGRect) searchRect withZoomLevel:(CGFloat)zoomLevel{
    //searchrect和四叉树区域rect无交集
    if ([self isRect:searchRect intersectsWith:_rect] == NO) {
        return [NSArray array];
    }
    
    NSMutableArray *array = [NSMutableArray array];
    
    //searchrect包含四叉树区域
    if ([self rect:searchRect containsRect:_rect]) {
        [array addObjectsFromArray:_quadItems];
    } else {
        for (HDAnnotation *item in _quadItems) {
            CGPoint p = CGPointMake((item.originalPoint.x/PointParameter)*zoomLevel, (item.originalPoint.y/PointParameter)*zoomLevel);
            item.point = p;

            if ([self rect:searchRect containsPt:item.point]) {
                [array addObject:item];
            }
        }
    }
    
    if(_childrens != nil && _childrens.count == 4) {
        for (HD_LD_ClusterQuadtree *children in _childrens) {
            [array addObjectsFromArray:[children searchInRect:searchRect withZoomLevel:(CGFloat)zoomLevel]];
        }
    }
    
    return array;
}

//rect是否相交
- (BOOL)isRect:(CGRect) rect1 intersectsWith:(CGRect) rect2 {
    CGFloat maxx = MAX(rect1.origin.x, rect2.origin.x);
    CGFloat minx = MIN(rect1.origin.x + rect1.size.width, rect2.origin.x + rect2.size.width);
    if (maxx - minx > 0) {
        return NO;
    }
    CGFloat maxy = MAX(rect1.origin.y, rect2.origin.y);
    CGFloat miny = MIN(rect1.origin.y + rect1.size.height, rect2.origin.y + rect2.size.height);
    if (maxy - miny > 0) {
        return NO;
    }
    return YES;
}

- (BOOL)rect:(CGRect) r1 containsRect:(CGRect) r2 {
    return r1.origin.x <= r2.origin.x && r1.size.width >= r2.size.width && r1.origin.y <= r2.origin.y && r1.size.height >= r2.size.height;
}


@end
